Search for: All records

We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $$n$$-node undirected graph. We provide a randomized algorithm that, with $$O(n\epsilon^{-2})$$ queries to a degree and neighbor oracle and in $$O(n\epsilon^{-3})$$ time, estimates the spectrum up to $$\epsilon$$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $$O(n\epsilon^{-7})$$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $$\epsilon$$, a $$2^{O(\epsilon^{-1})}$$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call \emph{nuclear sparsification}. We provide an $$O(n\epsilon^{-2})$$-query and $$O(n\epsilon^{-2})$$-time algorithm for computing $$O(n\epsilon^{-2})$$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first \emph{deterministic} algorithm for spectral density estimation that scales linearly with $$n$$ (sublinear in the representation size of the graph). 

We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function. 

We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most $$d^{1.25-\delta}$$ bits of memory must make at least $$\tilde{Omega}(d^{1+(4/3)\delta})$$ first-order queries (for any constant $$\delta in [0,1/4]$$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $$\tilde{O}(d)$$ query bound for this problem obtained by cutting plane methods that use $$\tilde{O}(d^2)$$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro. 

We consider the well-studied problem of completing a rank- , -incoherent matrix from incomplete observations. We focus on this problem in the semi-random setting where each entry is independently revealed with probability at least . Whereas multiple nearly-linear time algorithms have been established in the more specialized fully-random setting where each entry is revealed with probablity exactly , the only known nearly-linear time algorithm in the semi-random setting is due to [CG18], whose sample complexity has a polynomial dependence on the inverse accuracy and condition number and thus cannot achieve high-accuracy recovery. Our main result is the first high-accuracy nearly-linear time algorithm for solving semi-random matrix completion, and an extension to the noisy observation setting. Our result builds upon the recent short-flat decomposition framework of [KLLST23a, KLLST23b] and leverages fast algorithms for flow problems on graphs to solve adaptive reweighting subproblems efficiently 

The authors present an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an 𝑂 ~ ( 𝑛 log ⁡ 2 𝑛 ⋅ 𝜀 − 2 ) O ~ (nlog 2 n⋅ε −2 )-edge 𝜀 ε-approximate Eulerian sparsifier with high probability in 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 ) O ~ (mlog 3 n) time (where 𝑂 ~ ( ⋅ ) O ~ (⋅) hides polyloglog(n) factors). By a reduction from Peng-Song (STOC ’22), this yields an 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 + 𝑛 log ⁡ 6 𝑛 ) O ~ (mlog 3 n+nlog 6 n)-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially bounded weights with high probability, improving on the previous state-of-the-art runtime of Ω ( 𝑚 log ⁡ 8 𝑛 + 𝑛 log ⁡ 23 𝑛 ) Ω(mlog 8 n+nlog 23 n). They also provide a polynomial-time algorithm that computes sparsifiers with 𝑂 ( min ⁡ ( 𝑛 log ⁡ 𝑛 ⋅ 𝜀 − 2 + 𝑛 log ⁡ 5 / 3 𝑛 ⋅ 𝜀 − 4 / 3 , 𝑛 log ⁡ 3 / 2 𝑛 ⋅ 𝜀 − 2 ) ) O(min(nlogn⋅ε −2 +nlog 5/3 n⋅ε −4/3 ,nlog 3/2 n⋅ε −2 )) edges, improving the previous best bounds. Furthermore, they extend their techniques to yield the first 𝑂 ( 𝑚 ⋅ polylog ( 𝑛 ) ) O(m⋅polylog(n))-time algorithm for computing 𝑂 ( 𝑛 𝜀 − 1 ⋅ polylog ( 𝑛 ) ) O(nε −1 ⋅polylog(n))-edge graphical spectral sketches, along with a natural Eulerian generalization. Unlike prior approaches using short cycle or expander decompositions, their algorithms leverage a new effective resistance decomposition scheme, combined with natural sampling and electrical routing for degree balance. The analysis applies asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory.